Typical embedded systems, such as handheld computer systems, telephones, etc., provide computing functionality to a user while consuming a relatively small amount of space. Indeed, most embedded systems have relatively strict space requirements, which include a limitation on memory space. Consequently, program code designed to operate on such embedded systems is preferably optimized in one form or another to reduce the size of that code, such that the amount of memory consumed by storing the code on the embedded system is reduced.
A known method or system of reducing memory consumption of executable code relates to the use of byte-code interpreters. That is, systems have been designed to compile high-level computer programs into an intermediate level program, sometimes referred to as a byte code, which may be “executed” by a byte-code interpreter. Other systems may use another term, such as “p-code” instead of “byte code”. The resulting byte code is relatively smaller in size than the more traditional machine language executable form of a computer program, such that storing the byte code consumes less memory. Further, the interpreter is merely another computer program designed to receive byte code and directly execute the byte code without further compilation. The resulting combination of the interpreter and byte-code programs generally consumes significantly less memory space than compiled machine code.
Although the byte code/interpreter combination is useful in conserving memory consumption, additional efforts have been made to further reduce the size of the resulting byte code. Indeed, even with the use of interpreter, as programs grow in functionality and complexity, the interpretable byte code still consumes a significant amount of space. One method of reducing memory consumption relates to compressing the existing code. Compressing program code generally reduces the amount of memory consumed by the code itself without modifying the functional characteristics of the code that are noticeable to the user. When compressed code is executed, since some accommodations may need to be made for the compressed code, performance may be relatively slower than execution of uncompressed code. However, this tradeoff is often an acceptable drawback since the reduction in performance may be minimal in comparison to the highly desired reduction in memory consumption.
One compression technique relates to dictionary-based code compressors that associate a new code instruction with a common sequence or “phrase” of command instructions in either the original program or in a generic cross-section of known programs. The new instruction is created to replace the sequence of commands. Typically, the known sequence of commands is still stored in memory, i.e., in a dictionary, and this sequence is called during execution of the new, replacement instruction. Memory is conserved in that the new code instruction, taking the space of only one instruction, may be used to replace each occurrence of the sequence of commands, while storing the sequence of commands only once. However, since the sequence(s) must be stored in a persistent manner, dictionary-based compression algorithms still consume a significant amount of memory. Moreover, special arrangements must be made for the additional dictionary memory, including recognition of the dictionary address, among others.
Another solution relates to the use of a “Quote/EndQuote” command combination. Essentially, during the compression phase, the byte code is analyzed for repeating sequences, and instead of putting the sequences in a dictionary, the first sequence or phrase is stored in the program memory in a relatively normal manner. However, an “EndQuote” command or instruction is inserted at the end of the phrase. The EndQuote command acts as a delimiter for the repeated phrase. Also a “Quote” command is inserted in place of the next and subsequent phrases that repeat this earlier phrase. The Quote has a pointer which points to the beginning of the phrase earlier in the program memory thereby compressing the byte code. Later, during interpretation, each time a Quote command is encountered, the interpreter jumps to the beginning of the sequence and begins interpreting/executing the commands in the repeated phrase. This process continues until the interpreter reaches an End Quote command, which causes the program flow to jump back to the next byte code instruction, i.e., the one immediately following the Quote instruction.
The Quote/EndQuote combination overcomes some of the problems associated with the dictionary-based methods since the sequence is stored in a place where it was needed anyway and uses the same memory and address space as the rest of the program code. Unfortunately however, the Quote/EndQuote system has some drawbacks. For instance, two commands must be used, i.e., a Quote and an EndQuote command, for each sequence. Furthermore, if a portion of one repeated phrase overlaps with another repeated phrase, then two Quote commands must be used to compress one of the phrases. For example, assuming instructions 111 through 123 are repeated numerous times such that the phrase is marked with an EndQuote delimiter. Additionally, assume that instructions 115 through 129 are also repeated numerous times such that the phrase is also marked with an EndQuote delimiter. Using the Quote/EndQuote method, in order to Quote the second phrase, a first Quote instruction must be used to process instructions 115 to 123 and a second Quote instruction must be used to process the remaining instructions through to instruction 129. The reason why a second Quote instruction is needed is because of the EndQuote delimiter that is encountered immediately following instruction 123 which ends the execution of the phrase and causes flow to jump back to the instruction immediately following the first Quote instruction.
Another issue with respect to the Quote/EndQuote method relates to the fact that the known systems do not support nesting of repeated phrases. The nesting of phrases relates to Quoting a phrase that contains another Quote instruction within the repeated phrase. In known systems, the process operates in a manner that simply stores the program counter value in a register once a Quote instruction is encountered. The register is then checked upon reaching an EndQuote instruction. If the register holds a value stored by a Quote instruction, then the processor copies the register into the program counter and clears the register; flow continues after the original Quote instruction. If the register has no value stored therein, such as the first time the phrase is interpreted, then flow simply proceeds to the next instruction immediately following the EndQuote instruction. Using this approach, only one Quote instruction can be implemented as multiple return values cannot be stored.
It is with respect to these and other considerations that the present invention has been made.